package algorithm.dynamic_programming;


public class SplitNumber {

    public static int ways(int n){
        if(n <= 0)
            return 0;
        return process(1, n);
    }

    public static int process(int pre, int rest){
        if(pre == rest || rest == 0)
            return 1;
        if(pre > rest)
            return 0;
        int ways = 0;
        for (int i = pre; i <= rest ; i++) {
            ways += process(i, rest - i);
        }
        return ways;
    }

    public static int ways2(int n){
        if(n <= 0)
            return 0;
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 1; i < dp.length; i++) {
            dp[i][0] = 1;
            dp[i][i] = 1;
        }

        for (int i = dp.length - 2; i >= 1; i--) {
            for (int j = i + 1; j < dp[0].length; j++) {
                dp[i][j] = dp[i + 1][j] + dp[i][j - i];
            }
        }


        return dp[1][n];
    }


    public static void main(String[] args) {
        System.out.println(ways(10));
        System.out.println(ways2(10));
    }

}
